package daily.year2024.m9;

import contest.year2022.m7.m7d9.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树
 *
 * @author wjs 2024/9/1
 */
public class d1 {

    //解法一：dfs+前缀和
    //垃圾代码，效率非常差
    class Solution1 {
        int res;
        long target;

        public int pathSum(TreeNode root, int targetSum) {
            res = 0;
            target = targetSum;
            dfs(root, new ArrayList());
            return res;
        }

        // 维护一个累计值list，每一层就对应一个list
        private void dfs(TreeNode node, List<Long> sumList) {
            if (node == null) {
                return;
            }
            if (!sumList.isEmpty()) {
                for (int i = 0; i < sumList.size(); i++) {
                    long val = sumList.get(i);
                    if (val + node.val == target) {
                        res++;
                    }
                    sumList.set(i, val + node.val);
                }
            }
            if (node.val == target) {
                res++;
            }
            sumList.add((long) node.val);
            dfs(node.left, sumList);
            dfs(node.right, sumList);
            sumList.remove(sumList.size() - 1);
            for (int i = 0; i < sumList.size(); i++) {
                long val = sumList.get(i);
                sumList.set(i, val - node.val);
            }
        }
    }
}
